/*
给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。

例如，如果这个列表是 ["time", "me", "bell"]，我们就可以将其表示为 S = "time#bell#" 和 indexes = [0, 2, 5]。

对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到 "#" 结束，来恢复我们之前的单词列表。

那么成功对给定单词列表进行编码的最小字符串长度是多少呢？

 

示例：

输入: words = ["time", "me", "bell"]
输出: 10
说明: S = "time#bell#" ， indexes = [0, 2, 5] 。
 

提示：

1 <= words.length <= 2000
1 <= words[i].length <= 7
每个单词都是小写字母 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/short-encoding-of-words
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

执行用时 :92 ms, 在所有 C++ 提交中击败了82.47%的用户
内存消耗 :12.1 MB, 在所有 C++ 提交中击败了95.00%的用户

复杂度分析：
若vector 大小为n，string大小为m
翻转O(m x n),排序 O(m x n),扫描 O(n)
综上O(m x n)

*/
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minimumLengthEncoding(vector<string>& words) {
        //参考讨论区的解法，太妙了，原来代码还能这样写
        for (auto& s:words) {		//这种for循环要试着自己写
            reverse(s.begin(),s.end());
        }
        sort(words.begin(),words.end());	//直接用迭代器和STL中的sort排序
        int ans = 0;
        for (unsigned int i = 0;i < words.size()-1;i++) {       //这里注意边界
            int size = words[i].size();
            if (words[i] == words[i+1].substr(0,size)) {
                continue;	//如果在前n-1个元素当中，前一个是后一个串的子串，跳过
            }
            ans += size+1;	//如果前面的串不是后面串的子串，把长度加在结果上，并且加上分隔符#
        }
        return ans+words.back().size()+1;	//最后一个元素还没统计，加上即可
    }
};
int main(int argc, char const* argv[]){
	Solution s;
	std::vector<string> v = {"time","me","flajfbell","zell"};
	cout<<s.minimumLengthEncoding(v)<<endl;
	cout<<v[2].substr(1,-2)<<endl;	 	//sbustr(int a,int b) 如果a小于0或者a大于原串的长度会抛出异常
										//如果b不在范围内会到原串结尾而不是抛出异常
	return 0;
}
